<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <title>二分查找</title>
  </head>

  <body>
    <script>
      /*
       * 二分查找，又叫折半查找，思路：
       * 1.先从有序数组的最中间元素开始查找，如果和要查找的元素相等，直接返回索引，若不相等则下一步。
       * 2.如果指定的元素大于或者小于中间元素，则在大于或小于的那一半区域内查找，重复第一步直到找到目标元素
       *
       * 前提条件：
       * 1. 数组必须是有序的（递增/递减）
       * 2. 左右边有界
       */

      var binaryArr = [10, 14, 21, 38, 45, 47, 53, 81, 87, 99];
      var target = 47;
      console.log(binarySearch(binaryArr, target));

      /*
       * array: 被查找数组
       * target：查找的目标值
       */
      function binarySearch(array, target) {
        var left = 0, //左侧索引值
          right = array.length - 1; //右侧索引值

        while (left <= right) {
          //循环到什么时候结束呢？ 我们循环的过程中， low 和 higt 两个值会逐渐逼近
          var mid = Math.floor((left + right) / 2); //中间索引

          if (array[mid] == target) {
            //判断 中间值是否等于 我们要查的那个数，如果等于，那就找到了，直接返回
            return mid;
          } else if (target < array[mid]) {
            //判断 target 是否 < 中间值， 如果小于  说明我们要找的数，在左边那块
            right = mid - 1;
          } else if (target > array[mid]) {
            //判断 target 是否 > 中间值， 如果小于  说明我们要找的数，在右边那块
            left = mid + 1;
          }
        }
        return -1; //找不到返回-1
      }
    </script>
  </body>
</html>
